import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        List<List<Integer>> list = threeSum(nums);
        System.out.println(list);
    }
    //c
    public boolean isHappy(int n) {
        //循环一定有环，判断是否有环
        int slow = n;
        int fast = square(n);
        while(slow != fast) {
            if(fast == 1) {
                return true;
            }
            slow = square(slow);
            fast = square(fast);
            fast = square(fast);
        }
        return fast == 1;
    }
    //各位数字平方和计算
    public int square(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n%10);
            n = n / 10;
        }
        return sum;
    }
    //盛水最多的容器
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length-1;
        int ret = 0;
        while(left < right) {
            ret = Math.max(ret,Math.min(height[left],height[right]) * (right - left));
            if(height[left] > height[right]) {
                right--;
            }else{
                left++;
            }
        }
        return ret;
    }
    //有效三角形个数
    public int triangleNumber(int[] nums) {
        //排序
        Arrays.sort(nums);
        int n = nums.length-1;
        int sum = 0;
        //固定最大的数,遍历前面的数字
        for(int i = n; i >= 0; i--) {
            int left = 0;
            int right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    sum += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return sum;
    }
    //两数之和
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for(int i = 0; i  < n; i++) {
            for(int j = i+1; j < n; j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
    //两数之和，输入有序数组
    public static int[] twoSum2(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        while(left < right) {
            if(numbers[left] + numbers[right] > target) {
                right--;
            }else if(numbers[left] + numbers[right] < target) {
                left++;
            }else{
                return new int[]{left,right};
            }
        }
        return null;
    }
    //三数之和
    public static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        //排序
        Arrays.sort(nums);
        //固定一个数，找到两数之和
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < n;) {
            //计算两数和是否等于固定的数字的相反数
            int tmp = nums[i];
            twoSum(i,nums,ret);
            while( i < n && nums[i] == tmp) {
                i++;
            }
        }
        return ret;
    }
    public static void twoSum(int start, int[] nums, List<List<Integer>> ret) {
        int left = start + 1;
        int right = nums.length-1;
        int target = -nums[start];
        while(left < right) {
            if(nums[left] + nums[right] > target) {
                right--;
            }else if (nums[left] + nums[right] < target) {
                left++;
            }else{
                ret.add(Arrays.asList(nums[start],nums[left],nums[right]));
                //去重,两个数字相同，一直排除
                int tmp = nums[left];
                while(left < right && nums[left] == tmp) {
                    left++;
                }
            }
        }
    }
}
